package com.yun.algorithm.sort;

import java.util.Arrays;

public class HeapSort {

    public static void sort(int[] a) {
        heapify(a,a.length);
        for (int right = a.length-1; right > 0; right--) {
            swap(a,0,right);
            down(a,0,right);
        }
    }

    //建堆 O(n)
    private static void heapify(int[] array, int size) {
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(array,i,size);
        }
    }

    //下潜
    private static void down(int[] array, int parent, int size) {
        while (true) {
            int left = parent * 2 + 1;
            int right = left + 1;
            int max = parent;
            if (left < size && array[max] < array[left]) {
                max = left;
            }
            if (right < size && array[max] < array[right]) {
                max = right;
            }
            if (max == parent) {//没找到更大孩子
                break;
            }
            swap(array, max, parent);
            parent = max;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
